from typing import List
from collections import defaultdict
from collections import Counter

class Node:
    def __init__(self, char, size=0):
        self.char = char
        self.size = size
        self.children = defaultdict(Node)

def build_prefix_tree(words):
    root = Node('')
    for word in words:
        node = root
        for c in word:
            if c in node.children:
                node = node.children[c]
            else:
                node.children[c] = Node(c)


def init_tree_size(root):
    def init_size(node):
        if not node.children:
            node.size = 1
            return
        for child in node.children:
            node.size += init_size(child)
    init_size(root)


def search_prefix_tree(root, s, word_len):
    # todo: init_size
    def search_one(root, word):
        node: Node = root
        for c in word:
            if node.size >= 1 and c in node.children and node.children[c].size >= 1:
                node = node.children[c]
            else:
                return False
        else:
            for c in word:
                node.size -= 1
                node = node.children[c]
            return True

    success_cnt = 0
    for i in range(0, len(s), word_len):
        word = s[i: i+word_len]
        if not search_one(root, word):
            success = False
            break
        success_cnt += 1
    else:
        success = True

    for i in list(range(0, len(s), word_len))[:success_cnt]:
        word = s[i: i+word_len]
        node = root
        for c in word:
            node.size += 1
            node = node.children[c]
    return success


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        sum_len = len(words) * len(words[0])
        if len(s) < sum_len:
            return []

        target_stat = Counter(c for word in words for c in word)
        valid_positions = []
        stat = defaultdict(int)
        for i in range(len(s)):
            if i + sum_len >= sum_len:
                break
            stat[s[i]] += 1
            if i - sum_len >= 0:
                stat[s[i - sum_len]] -= 1
            if stat == target_stat:
                valid_positions.append(i)

        result = []
        root = build_prefix_tree(words)
        init_tree_size(root)
        for i in valid_positions:
            if search_prefix_tree(root, s[i: i+sum_len], len(words[0])):
                result.append(i)
        return result

